//
// Created by francklinson on 2021/7/11.
//
//你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。
//若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。
//池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;


class Solution {
private:
    vector<int> ret;
    vector<pair<int, int>> movement{{1,  0},
                                    {-1, 0},
                                    {0,  1},
                                    {0,  -1},
                                    {-1, -1},
                                    {-1, 1},
                                    {1,  -1},
                                    {1,  1}};
public:
    /**
     *统计各个池塘的大小
     * @param land
     * @return
     */
    vector<int> pondSizes(vector<vector<int>> &land) {
        for (int i = 0; i < land.size(); ++i) {
            for (int j = 0; j < land[0].size(); ++j) {
                if (land[i][j] == 0) {
//                    BFS(land, i, j);  /// BFS
                    ret.push_back(DFS(land, i, j)); ///DFS
                }
            }
        }
        sort(ret.begin(), ret.end());
        return ret;
    }

    void BFS(vector<vector<int>> &land, int i, int j) {
        int pondSize = 0;
        queue<pair<int, int>> q;
        q.emplace(i, j);
        land[i][j] = 1;
        while (!q.empty()) {
            auto p = q.front();
            q.pop();
            ++pondSize;
            for (int k = 0; k < 8; ++k) {
                int nextI = p.first + movement[k].first;
                int nextJ = p.second + movement[k].second;
                if (nextI >= 0 and nextI < land.size() and nextJ >= 0 and nextJ < land[0].size() and
                    land[nextI][nextJ] == 0) {
                    q.emplace(nextI, nextJ);
                    land[nextI][nextJ] = 1;
                }
            }
        }
        ret.push_back(pondSize);
    }

    int DFS(vector<vector<int>> &land, int i, int j) {
        land[i][j] = 1;
        int area = 1;
        for (int k = 0; k < 8; ++k) {
            int nextI = i + movement[k].first;
            int nextJ = j + movement[k].second;
            if (nextI >= 0 and nextI < land.size() and nextJ >= 0 and nextJ < land[0].size() and
                land[nextI][nextJ] == 0) {
                area += DFS(land, nextI, nextJ);
            }
        }
        return area;
    }
};

int main() {
    vector<vector<int>> land{{0, 2, 1, 0},
                             {0, 1, 0, 1},
                             {1, 1, 0, 1},
                             {0, 1, 0, 1}};
    Solution sol;
    auto ans = sol.pondSizes(land);
    for (auto &x:ans) {
        cout << x;
        cout << " ";
    }
    return 0;
}